#include "binarytree.h"
#include <iostream>
BinaryTree::BinaryTree()
{
    root = nullptr;
    this->showptr = nullptr;
    this->cmpptr = nullptr;
}

BinaryTree::BinaryTree(void (*showptr)(const ElementType &), int (*cmpptr)(const ElementType &, const ElementType &))
{
    this->showptr = showptr;
    this->cmpptr = cmpptr;
    root = nullptr;
}

BinaryTree::~BinaryTree()
{

    FreeNode(root);
}

void BinaryTree::Insert(const ElementType &element)
{

    root = InsertNode(root, element);
}

void BinaryTree::show()
{
    std::cout << "前：";
    PrevTravel(root);
    std::cout << std::endl;

    std::cout << "中：";
    MidTravel(root);
    std::cout << std::endl;

    std::cout << "后：";
    PostTravel(root);
    std::cout << std::endl;
}

ElementType *BinaryTree::Find(const ElementType &element)
{

    return FindNode(root, element);
}

void BinaryTree::RemoveByElement(const ElementType &element)
{

    root = Remove(root, element);
}

BinaryTree::TreeNode *BinaryTree::InsertNode(TreeNode *node, const ElementType &element)
{ // 递归中止
    if (node == nullptr)
    {
        return new TreeNode(element);
    }
    // 二叉树数据唯一
    if (node->value == element)
    {
        return node;
    }
    if (node->value > element)
    { // 递归插入左子树
        node->left = InsertNode(node->left, element);
        // 左边重
        if (LRDev(node) > 1)
        { // 左左失衡
            if (element < node->left->value)
            {
                node = RotateRight(node);
            }
            else
            {
                node = RotateLeftRight(node);
            }
        }
    }
    else
    {
        // 插入右子树
        node->right = InsertNode(node->right, element);
        if (LRDev(node) < -1)
        {
            if (node->right->value < element)
            {
                // 右右
                node = RotateLeft(node);
            }
            else
            {
                node = RotateRightLeft(node);
            }
        }
    }

    return node;
}

void BinaryTree::PrevTravel(TreeNode *node)
{
    if (node == nullptr)
        return;
    showptr(node->value);
    PrevTravel(node->left);
    PrevTravel(node->right);
}

void BinaryTree::MidTravel(TreeNode *node)
{
    if (node == nullptr)
        return;

    PrevTravel(node->left);
    showptr(node);
    PrevTravel(node->right);
}

void BinaryTree::PostTravel(TreeNode *node)
{
    if (node == nullptr)
        return;
    PrevTravel(node->left);
    PrevTravel(node->right);
    showptr(node);
}

void BinaryTree::FreeNode(TreeNode *node)
{
    if (node == nullptr)
    {
        return;
    }
    FreeNode(node->left);
    FreeNode(node->right);
    delete node;
}

ElementType *BinaryTree::FindNode(TreeNode *node, const ElementType &element)
{
    if (node == nullptr)
    {
        return nullptr;
    }

    // if (element == node->value)
    if (cmpptr(element, node->value) == 2)
    {
        return &node->value;
    }
    // else if (element > node->value)
    else if (cmpptr(element, node->value) == 1)
    {
        FindNode(node->right, element);
    }
    // else if (element < node->value)
    else if (cmpptr(element, node->value) == 0)
    {
        FindNode(node->left, element);
    }
}

BinaryTree::TreeNode *BinaryTree::Remove(TreeNode *node, const ElementType &element)
{
    if (node == nullptr)
        return nullptr;
    if (cmpptr(element, node->value) == 0)
        node->right = Remove(node->right, element);
    else if (cmpptr(element, node->value) == 1)
        node->left = Remove(node->left, element);
    else
    {
        if (node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr;
        }
        else if (node->left != nullptr && node->right != nullptr)
        { // 取右子树中最小的节点
            TreeNode *min = GetMinNode(node->right);
            node->value = min->value;
            node->right = Remove(node->right, min->value);
        }
        else
        { // 只有一个子节点
            // TreeNode *childNode = node->left ? node->left : node->right;
            TreeNode *childNode;
            if (cmpptr(node->left, node->right) == 1)
            {
                childNode = node->left;
            }
            else
            {
                childNode = node->right;
            }

            delete node;
            node = childNode;
        }
    }

    if (LRDev(node) > 1)
    { // 左右失衡
        if (LRDev(node->left) > 0)
        {
            node = RotateLeftRight(node);
        }
        else
        {
            node = RotateRight(node);
        }
    }
    if (LRDev(node) < -1)
    {
        if (LRDev(node->right) < 0)
        {
            // 右右
            node = RotateLeft(node);
        }
        else
        {
            node = RotateRightLeft(node);
        }
    }
    return node;
}

BinaryTree::TreeNode *BinaryTree::GetMinNode(TreeNode *node)
{
    TreeNode *minNode = node;
    while (minNode->left != nullptr)
        minNode = minNode->left;
    return minNode;
}

BinaryTree::TreeNode *BinaryTree::RotateRight(TreeNode *node)
{
    TreeNode *t = node->left;
    node->left = t->right;
    t->right = node;
    return t;
}

BinaryTree::TreeNode *BinaryTree::RotateLeft(TreeNode *node)
{
    TreeNode *t = node->right;
    node->right = t->left;
    t->left = node;
    return t;
}

BinaryTree::TreeNode *BinaryTree::RotateLeftRight(TreeNode *node)
{ // 左子树左旋
    node->left = RotateLeft(node->left);
    // 整棵树右旋
    return RotateRight(node);
}

BinaryTree::TreeNode *BinaryTree::RotateRightLeft(TreeNode *node)
{ // 右子树右旋
    node->right = RotateRight(node->right);
    // 所有的左旋
    return RotateLeft(node);
}

int BinaryTree::GetNodeHight(TreeNode *node)
{
    if (node == nullptr)
    {
        return 0;
    }
    int lefthight = GetNodeHight(node->left);
    int righthight = GetNodeHight(node->right);
    return (lefthight > righthight ? lefthight : righthight) + 1;
}

int BinaryTree::LRDev(TreeNode *node)
{
    if (node == nullptr)
        return 0;
    return GetNodeHight(node->left) - GetNodeHight(node->right);
}

bool BinaryTree::IsComTree1(TreeNode *node)
{  
    if(node->left==nullptr||node->right==nullptr)
        return false;
    bool a=IsComTree1(node->right);
    bool b=IsComTree1(node->left);
    if (a&&b)
    {
        return true;
    }
    return false;
}

int BinaryTree::Count1(TreeNode *node)
{   static int count1=0;
    static int count2=0;
    if (node==nullptr)
    {
        return;
    }
    Count1(node->left);
    Count1(node->right);
    if (node->left==nullptr&&node->right==nullptr)
    {
        count1++;
    }
     if (node->left!=nullptr&&node->right!=nullptr)
    {
        count2++;
    }
    count1++;
    if (node==root)
    {
        std::cout<<"度为1："<<count1<<std::endl;
        std::cout<<"度为2："<<count2<<std::endl;

    }
    
}

bool BinaryTree::IsComTree()
{
    return IsComTree1(root);
}

void BinaryTree::Count()
{
    Count1(root);
}
